快速排序法(Quick Sort)又稱分割交換排序法，是目前公認效率極佳的演算法，使用了分治法(Divide and Conquer)的概念。原理是先從原始資料列中找一個基準值(Pivot)，接著逐一將資料與基準值比較，小於基準值的資料放在左邊，大於基準值的資料放在右邊，再將兩邊區塊分別再找出基準值，重複前面的步驟，直到排序完為止。

常用的基準值(Pivot)選擇方式:

• 選擇第1筆或最後1筆的資料
• 隨機亂數
• 三數中位數(Median-of-three)，第一、中間、最後筆資料，排序之後取中間的值(Musser, 1997)。
  例如: 1,5,9,6,3，取出1,9,3，排序後1,3,9，取3為基準點。

平均時間複雜度為: O(n log n)

由於快速排序法有多種實作版本，下面介紹常見的3種實作版本。

遞迴版本

此版本雖然容易理解，但會影響到空間複雜度，每次都需要申請兩個子數列的記憶體空間，遞迴的深度越多，需要記憶體空間就越大。

操作流程:

1. 資料列中找出一個基準值(Pivot)
2. 將小於Pivot的資料放在左邊，大於Pivot的資料放在右邊
3. 左右兩邊資料分別重複1~2步驟，直到剩下1筆資料
4. 合併

下面利用50 90 70 20 10 30 40 60 80由小到大排序。

JavaScript

let data = [50,90,70,20,10,30,40,60,80]

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let left = [];
  let right = [];
  let pivot = arr[0];
  for (let i = 1; i < arr.length; i++) {
    let num = arr[i];
    if (num < pivot) {
      left.push(num);
    } else {
      right.push(num);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort(data))//[10, 20, 30, 40, 50, 60, 70, 80, 90]

Python

#Quick Sort
def QuickSort(arr):
    n = len(arr)
    if n <= 1:
        return arr
    left = []
    right = []
    pivot = arr[0]
    for i in range(1,n):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return QuickSort(left) + [pivot] + QuickSort(right)

data = [50,90,70,20,10,30,40,60,80]

print(QuickSort(data))#[10, 20, 30, 40, 50, 60, 70, 80, 90]

原地交換版本(In-Place)-Lomuto partition scheme

基於Lomuto partition scheme的原理，原始資料列使用一個指標與索引，當索引的資料小於Pivot時，索引的資料與指標位置資料交換。

前面的版本會需要額外的記憶體空間，In-Place版本不需要額外的子數列記憶體空間，因為只會更改原本的數列，切割的同時也就等同合併了，所以只需花費常數O(1)的空間複雜度。實作時會需要用到Partition輔助函式，來直接分割原本的數列。

操作流程:

1. 資料列最後一筆設定為基準值(Pivot)
2. 設定一個指標指向資料列第一筆，用來記錄小於Pivot的資料位置
3. 逐一與Pivot比較
4. 若當前資料小於Pivot，就將該資料與指標位置的資料做交換，接著指標往下一個位置移動
5. 若當前資料大於等於Pivot，則跳過不做任何動作
6. 當所有資料比較過後，再將Pivot與指標位置的資料交換
7. 左右兩邊資料列分別重複1~6步驟，直到剩下1筆分割交換完成，不須合併

下面利用90 40 10 60 70 30 80 20 50由小到大排序。

單回合細節圖

每回合簡略圖

JavaScript

let data = [90, 40, 10, 60, 70, 30, 80, 20, 50];

function quickSort(arr, start, end) {
  if (start < end) {
    const pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, end);
  }
  return arr
}

function partition(arr, start, end) {
  let pivot = arr[end];
  let nextIndex = start;
  for (let i = start; i < end; i++) {
    if (arr[i] < pivot) {
      [arr[nextIndex],arr[i]] = [arr[i],arr[nextIndex]]
      nextIndex++;
    }
  }
  [arr[nextIndex],arr[end]] = [arr[end],arr[nextIndex]]  
  return nextIndex
}

console.log(quickSort(data, 0, data.length - 1)) //[10, 20, 30, 40, 50, 60, 70, 80, 90]

Python

def QuickSort(arr, start, end):
    if start < end:
        pivotIndex = partition(arr, start, end)
        QuickSort(arr, start, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, end)
    return arr

def partition(arr, start, end):
    n = len(arr)
    pivot = arr[end]
    nextIndex = start
    for i in range(start,n-1):
        if arr[i] < pivot:
            arr[nextIndex],arr[i] = arr[i],arr[nextIndex]
            nextIndex += 1
    arr[nextIndex],arr[end] = arr[end],arr[nextIndex]
    return nextIndex

data = [50,90,70,20,10,30,40,60,80]

print(QuickSort(data, 0 , len(data)-1))
#[10, 20, 30, 40, 50, 60, 70, 80, 90]

原地交換版本(In-Place)-Hoare partition scheme

基於Hoare partition scheme的原理，將原始資料列使用兩個指標，從資料列的兩端開始相互移動，直到它們相遇或反轉為止。

操作流程:

1. 資料列中找出一個基準值(Pivot)
2. 最左邊有一個指標(Pointer) L，最右邊也有一個指標(Pointer) R
3. L逐一往右移動直到找到大於Pivot停下來
4. R逐一往左移動直到找到小於Pivot停下來
5. L與R的資料互相交換，L與R繼續移動
6. L與R重疊時，重疊位置的資料Pivot互相交換
7. L與R反轉時，R位置的資料與Pivot互相交換
8. 基準值的左右兩邊資料分別重複1~7步驟，直到剩下1筆分割交換完成，不須合併

下面利用30 10 40 5 70 15 60 20 50 25由小到大排序。

單回合細節圖

每回合簡略圖

JavaScript

let data = [30,10,40,5,70,15,60,20,50,25];

function quickSort(arr, start, end) {
  if (start < end) {
    let pivotIndex = partition(arr, start, end);
    quickSort(arr, start, pivotIndex-1);
    quickSort(arr, pivotIndex + 1, end);
  }
  return arr;
}

function partition(arr, start, end) {
  let pivot = arr[start]
  let leftPointer = start+1
  let rightPointer = end
  let done = false
  while (done===false) {
    while (leftPointer <= rightPointer&&arr[leftPointer] <= pivot) {
      leftPointer +=1
    }

    while (leftPointer <= rightPointer&&arr[rightPointer] >= pivot) {
      rightPointer -=1
    }

    if (leftPointer > rightPointer) {
      done = true
    }else{
      [arr[leftPointer],arr[rightPointer]]=[arr[rightPointer],arr[leftPointer]]
    }
  }
  [arr[start],arr[rightPointer]]=[arr[rightPointer],arr[start]]
  return rightPointer
}

console.log(quickSort(data, 0, data.length - 1))
//[5, 10, 15, 20, 25, 30, 40, 50, 60, 70]

Python

def QuickSort(arr, start, end):
    if start < end:
        pivotIndex = Partition(arr, start, end)
        QuickSort(arr, start, pivotIndex-1)
        QuickSort(arr, pivotIndex+1, end)
    return arr

def Partition(arr, start, end):
    pivot = arr[start]
    leftPointer = start+1
    rightPointer = end
    done = False
    while not done:
        while leftPointer <= rightPointer and arr[leftPointer] <= pivot:
            leftPointer += 1
        while arr[rightPointer] >= pivot and rightPointer >=leftPointer:
            rightPointer -= 1
        if rightPointer < leftPointer:
            done= True
        else:
            arr[leftPointer],arr[rightPointer] = arr[rightPointer],arr[leftPointer]
    arr[start],arr[rightPointer] = arr[rightPointer],arr[start]
    return rightPointer
    
        
data = [30,10,40,5,70,15,60,20,50,25]

print(QuickSort(data, 0 , len(data)-1))
#[5, 10, 15, 20, 25, 30, 40, 50, 60, 70]